package two.chapter_4.c4_2;

import edu.princeton.cs.algs4.Bag;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

/**
 * 有向图的可达性
 */
public class DirectedDFS {
    private boolean[] marked;
    public DirectedDFS(Digragh g,int s){
        marked=new boolean[g.v()];
        dfs(g,s);
    }

    public DirectedDFS(Digragh g,Iterable<Integer> sources){
        marked=new boolean[g.v()];
        for (int s:sources){
            if (!marked[s]){
                dfs(g,s);
            }
        }
    }
    private void dfs(Digragh g, int v) {
        marked[v]=true;
        for (int w:g.adj(v)){
            if (!marked[w]){
                dfs(g,w);
            }
        }
    }

    public boolean marked(int v){
        return marked[v];
    }

    public static void main(String[]args){
        String graph="/Users/wind/downloads/高焕堂EIT/Algorithms-master/data/tinyDG.txt";
        Digragh g=new Digragh(new In(graph));
        Bag<Integer> sources=new Bag<>();
        String args_[]={"1","2","6"};
        for (int i=0;i<args_.length;i++){
            sources.add(Integer.parseInt(args_[i]));
        }
        DirectedDFS reachable=new DirectedDFS(g,sources);
        for (int v=0;v<g.v();v++){
            if (reachable.marked[v]){
                StdOut.print(v+" ");
            }
        }
        StdOut.println();
    }
}
